/**
 * 双向链表节点构造函数
 * @param {*} data 节点值
 * @param {DoubleNode} last 节点上一个
 * @param {DoubleNode} next 节点下一个
 */
function DoubleNode(data, last, next) {
	this.data = data;
	this.last = last;
	this.next = next;
}

/**
 * 双向链表的构造函数
 */
function DoubleLinkedList() {
	// 先初始化头结点
	this.head = new DoubleNode(null, null, null);
	// 双向链表也是循环链表，因此先开始头结点的前后指向自己
	this.head.last = this.head;
	this.head.next = this.head;
	/**
	 * 尾部加入一个元素
	 * @param {*} data 节点值
	 */
	this.add = (data) => {
		// 先索引至最后一个节点
		let node = this.head;
		while (node.next != this.head) {
			node = node.next;
		}
		// 实例化一个节点，让新节点前一个执行node，后一个指向head
		let newNode = new DoubleNode(data, node, this.head);
		// 再把node的下一个指向newNode
		node.next = newNode;
	}
	/**
	 * 指定位置插入
	 * @param {Number} index 插入位置，0代表第一个（即头结点的后一个）
	 * @param {*} data 插入值
	 */
	this.insert = (index, data) => {
		// 索引至第index - 1个节点
		let node = this.head;
		// 可以把头结点视为第-1个节点
		for (let i = -1; i < index - 1; i++) {
			node = node.next;
			if (node == this.head) {
				console.error('索引越界！');
				return;
			}
		}
		// 现在node指向第index - 1个节点
		// 实例化新节点
		let newNode = new DoubleNode(data, null, null);
		// 先把newNode下一个指向node的下一个
		newNode.next = node.next;
		// 再把此时newNode的下一个节点的上一个指向newNode
		newNode.next.last = newNode;
		// 再把newNode的上一个指向node
		newNode.last = node;
		// 再把node的下一个指向newNode
		node.next = newNode;
	}
	/**
	 * 删除节点
	 * @param {Number} index 待删除节点的索引
	 */
	this.delete = (index) => {
		// 索引至第index - 1个节点
		let node = this.head;
		for (let i = -1; i < index - 1; i++) {
			node = node.next;
			// 越界检测
			if (node.next == this.head) {
				console.error('索引越界！');
				return;
			}
		}
		// 现在node指向第index - 1个节点
		// 先把node的下一个指向node的下一个的下一个
		node.next = node.next.next;
		// 再把此时node的下一个的上一个指向node
		node.next.last = node;
	}
	/**
	 * 打印双向链表
	 */
	this.print = () => {
		let resultString = '○';
		let node = this.head;
		while ((node = node.next) != this.head) {
			resultString = resultString + ' <-> ' + node.data;
		}
		console.log(resultString);
	}
	// 修改和查询是差不多的，在此不再实现
}

// 测试
let list = new DoubleLinkedList();
// 加入5个
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.print();
// 插入两个
list.insert(0, 0);
list.insert(4, 10);
list.print();
// 删除一个
list.delete(4);
list.print();